package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class _39_CombinationSum {
    public static void main(String[] args) {
        Integer[] nums = {1, 6, 8, 2, 6, 9};
        List<Integer> arrayList = new ArrayList<>(Arrays.asList(1, 6, 8, 2, 6, 9));
        arrayList.forEach(System.out::println);
        Arrays.sort(nums, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        System.out.println(Arrays.toString(nums));
    }

    ;
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public void backtrack(int[] candidates, int target, int idx) {
        if (target < 0 || idx == candidates.length) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));  // 注意 : 这里需要创建一个新的 ArrayList
            return;
        }
        // 直接跳过
        backtrack(candidates, target, idx + 1);

        // 选择当前数
        path.add(candidates[idx]);
        backtrack(candidates, target - candidates[idx], idx);
        path.remove(path.size() - 1);

    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0);
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

